package edu.kpi.pzks2.tools;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Stack;

import edu.kpi.pzks2.graph.Edge;
import edu.kpi.pzks2.graph.Node;
import edu.kpi.pzks2.ui.MainFrame;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.util.Pair;

public class TaskGraphTools {
    public static DirectedSparseGraph<Node, Edge> generate(final GenerationParams params, boolean debug) {
        final DirectedSparseGraph<Node, Edge> graph = new DirectedSparseGraph<Node, Edge>();
        final List<Node> nodes = new ArrayList<Node>();
        
        int overallNodeWeight = 0;
        
        int nodeId = 0;
        for (int i = 0; i < params.getNodeCount(); i++) {
            int weight;
            if (params.getMaxNodeWeight() == params.getMinNodeWeight()) {
                weight = params.getMaxNodeWeight();
            } else {
                weight = new Random().nextInt(params.getMaxNodeWeight() - params.getMinNodeWeight()) +
                        params.getMinNodeWeight();
            }
            final Node node = new Node(nodeId++);
            node.setWeight(weight);
            graph.addVertex(node);
            overallNodeWeight += weight;
            nodes.add(node);
        }
        
        if (debug) {
            MainFrame.showLogMessage("\n==Generated graph==");
            MainFrame.showLogMessage("Node count " + params.getNodeCount());
            MainFrame.showLogMessage("Overall node weight " + overallNodeWeight);
        }
        
        int overallEdgeWeight = (int) (overallNodeWeight / params.getConnectivity()) - overallNodeWeight;
        int minEdgeW = params.getMinEdgeWeight();
        
        if (debug) {
            MainFrame.showLogMessage("Connectivity " + params.getConnectivity());
            MainFrame.showLogMessage("Overall edge weight " + overallEdgeWeight);
        }
        
        final Map<Pair<Integer>, Edge> edges = new HashMap<Pair<Integer>, Edge>();

        // Generate edge
        final Random rand = new Random();
        int edgeId = 0;
        while (overallEdgeWeight > 0) {
            int topLimit = 
                    Math.min(overallEdgeWeight - minEdgeW, params.getMaxEdgeWeight());
            int edgeWeight;
            if (overallEdgeWeight > minEdgeW) {
                edgeWeight = minEdgeW + rand.nextInt(topLimit);
            } else {
                edgeWeight = overallEdgeWeight;
            }
            
            overallEdgeWeight -= edgeWeight;
            if (overallEdgeWeight <= minEdgeW) {
                edgeWeight += overallEdgeWeight;
                overallEdgeWeight = 0;
            }
            final Edge edge = new Edge(edgeId++);
            edge.setWeight(edgeWeight);
            
            boolean insertSuccess = false;
            while (!insertSuccess) {
                final int from = rand.nextInt(params.getNodeCount());
                int to = rand.nextInt(params.getNodeCount());
                while (to == from) {
                    to = rand.nextInt(params.getNodeCount());
                }
                
                final Pair<Integer> pair = new Pair<Integer>(from, to);
                if (edges.containsKey(pair)) {
                    final Edge n = edges.get(pair);
                    n.setWeight(n.getWeight() + edgeWeight);
                    insertSuccess = true;
                } else {
                    graph.addEdge(edge, nodes.get(from), nodes.get(to));
                    
                    insertSuccess = dontHaveLoops(graph);
                    
                    if (!insertSuccess) {
                        graph.removeEdge(edge);
                    } else {
                        edges.put(new Pair<Integer>(from, to), edge);
                    }
                }
            }
        }
        
        return graph;
    }
    
    private static boolean deepSearch(Stack<Node> visited, DirectedGraph<Node, Edge> graph) {
        final Node currentNode = visited.peek();
        
        for (Edge e : graph.getIncidentEdges(currentNode)) {
            final Pair<Node> pair = graph.getEndpoints(e);
            if (pair.getFirst() == currentNode) {
                if (visited.contains(pair.getSecond())) return false;
                visited.push(pair.getSecond());
                if (!deepSearch(visited, graph)) return false;
                visited.pop();
            }
        }
        
        return true;
    }
    
    public static boolean dontHaveLoops(DirectedGraph<Node, Edge> graph) {
        boolean dontHaveCycles = true;
        for (Node n : graph.getVertices()) {
            final Stack<Node> visited = new Stack<Node>();
            visited.push(n);
            dontHaveCycles = deepSearch(visited, graph);
            if (!dontHaveCycles) break;
        }
        return dontHaveCycles;
    }
    
    /**
     * @param graph the graph
     * @param node node, for which we process crirical path
     * @param isTime true - critical path by time, false - critical path by length
     * @return critical path
     */
    public static int getCriticalPath(Graph<Node, Edge> graph, Node node, boolean isTime) {
        if (graph.getOutEdges(node).isEmpty()) {
            if (isTime) {
                return node.getWeight();
            } else {
                return 1;
            }
        }
        
        int maxPath = 0;
        for (Edge outEdge : graph.getOutEdges(node)) {
            final Node child = (Node) graph.getEndpoints(outEdge).getSecond();
            final int currentPath = getCriticalPath(graph, child, isTime);
            if (currentPath > maxPath) {
                maxPath = currentPath;
            }
        }
        
        if (isTime) {
            return maxPath + node.getWeight();
        } else {
            return maxPath + 1;
        }
    }

    public static int getMaxCriticalPath(final Graph<Node, Edge> graph) {
        int max = 0;
        
        for (Node node : graph.getVertices()) {
            int current = getCriticalPath(graph, node, true);
            max = (max < current) ? current : max;
        }
        
        return max;
    }
    
    public static int getOverallWeight(final Graph<Node, Edge> graph) {
        int sum = 0;
        
        for (Node node : graph.getVertices()) {
            sum += node.getWeight();
        }
        
        return sum;
    }
}
